匈牙利算法

匈牙利算法是一种在多项式时间内求解任务分配问题的组合优化算法

匈牙利算法有两张表达形式：矩阵表达形式、图论表达形式

矩阵表达形式

理论依据

（1）如果矩阵的所有元素aij≥0，而其中存在一组位于不同行、不同列的零元素，则它们必然对应目标函数取得最小

（2）将二维分配问题效用矩阵的任一行或者任一列中所有元素加上或者减去任意值，所得新效用矩阵对应的最优分配策略与原效用矩阵相同，最优解的值需要加上或者减去该任意值

算法流程：（该算法是求解最小化，对于最大化问题转换即可，可参考下例）

（1）找出矩阵每行的最小元素，并分别从每行中减去它

（2）再找出矩阵每列的最小元素，再分别从各列中减去它

（3）判断零元素是否位于不同行、不同列，如果出现，则结束，否则向下进行

（4）逐行找0，遇单0画线覆盖该0所在列，遇多0画线覆盖该行（也称为：用尽量少的线覆盖全部0）

（5）找出最小未被覆盖的元素

（6）未被覆盖的行减最小元素；被覆盖的列加上最小元素

（7）反复进行4、5、6操作直到出现不同行、不同列的0

有 4 种机械要分别安装在4个工地，它们在4个工地的工作效率不同，问应如何指派，可使4台机械发挥的总效益最大？l有 4 种机械要分别安装在4个工地，它们在4个工地的工作效率不同，问应如何指派，可使4台机械发挥的总效益最大？

（1）将最大化问题转换成最小化问题

b = max(a) - a   在此题中max(a)=43

（2）行减最小元素、列减最小元素

（3）未能找到不同行、不同列的0，继续进行

至此，我们找到了最优解的位置，所以最终结果：40+36+35+43=154